前言

大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
那就開始今天的解題吧~

Question

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

• 2 <= nums.length <= 10^5
• -30 <= nums[i] <= 30
• -10^9 <= target <= 10^9.
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

• 時間複雜度: O(n)
• 不能使用除法

Think

給一個陣列nums，須回傳一個陣列(後面稱ans)，其中ans每個位置的值為原來nums中，除了該位置以外所有值的乘積。

例如：

nums = [1, 2, 3, 4]
=> [2*3*4, 1*3*4, 1*2*4, 1*2*3]

先建一個長度跟nums一樣的list(ans)，每個位置都放1。

• 第一個迴圈是從index0~length-1，ans的下一個位置的值會是目前ans[index]乘上nums[index]

  • 此時ans: [1, 1*1, 1*2, (1*2)*3]
  • =>ans: [1, 1, 2, 6]
  • 只有ans index:3位置的值是完成的

• 接著，從index:2的位置開始逆向再做一次，但這次是ans[2]是ans[2]本身乘上前一個previous(=nums[3])，也就是(1*2)*4。

• 每次結束previous都得在乘上該次nums[index]的值

• End~

Code

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        ans = [1 for x in range(len(nums))]
            
        for index in range(len(nums)-1):
            ans[index+1] = ans[index] * nums[index]
        
        # print("ans: ", ans)
        
        previous = nums[len(nums)-1]
        
        for index in range(len(nums)-1-1, -1, -1):
            # print("index:", index, ", ans:", ans[index], ", previous:", previous)
            ans[index] = ans[index] * previous
            # print("Ans: ", ans, "\n")
            previous *= nums[index]
            # print("Change: ", previous)
                
        # print("ans: ", ans)
        return ans

Submission

今天就到這邊啦~
大家明天見